Как это ни
странно, но грибы очень любят сладкую воду. А Михаил любит с ней ещё и
экспериментировать. Каждый вид сладкой воды имеет свой уровень сладости. Перед
Михаилом стоят подряд n ёмкостей со
сладкой водой разных уровней. Если Михаил смешает две воды с уровнями x и y,
то вместо этих двух получится вода с уровнем сладости 2 * min(x, y).
Помогите Михаилу
получить воду с максимально возможным уровнем сладости.
Вход. Первая строка содержит количество
ёмкостей n (1 ≤ n ≤ 106). Вторая строка
содержит n целых чисел: уровни
сладостей xi (-109
≤ xi ≤ 109).
Выход. Вывести
максимально возможный уровень сладости, который можно получить путём смешивания
некоторых из имеющихся вод.
|
Пример входа |
Пример выхода |
|
3 1 3 6 |
6 |
жадность
Занесем все
емкости в мультимножество (в процессе смешивания могут появляться емкости с
одинаковым уровнем сладости). Смешивать воды со сладостями x и y есть смысл, если в
результате будет получаться вода с уровнем большим max(x, y).
Рассмотрим две
воды с наименьшими уровнями сладости x
и y.
·
Если 2x ≤ y, то после их
смешивания получится вода с уровнем сладости 2 * min(x, y) = 2x, что не больше y. В этом случае нет смысла производить смешивание: удалим из
мультимножества сладость x и
соответствующую емкость в дальнейшем рассматривать не будем.
·
Если 2x > y, то после их
смешивания получится вода с уровнем сладости 2 * min(x, y) = 2x, что больше y. Удаляем из мультимножества сладости x и y и добавляем
сладость 2x.
Производим
описанную операцию с двумя наименьшими сладостями x и y пока
мультимножество содержит более одного элемента.
Объявим рабочее
мультимножество.
multiset<long
long> m;
Читаем количество
емкостей n. Заносим уровни сладостей
имеющихся емкостей в мультимножество.
scanf("%d",&n);
for(i
= 0; i < n; i++)
{
scanf("%lld",&val);
m.insert(val);
}
Обрабатываем мультимножество, пока оно содержит более
одного элемента.
while(m.size()
> 1)
{
Извлекаем две наименьшие сладости a и b.
long long a = *m.begin(); m.erase(m.begin());
long long b = *m.begin();
Если при их смешивании получится сладость, большая max(a, b),
то производим смешивание и результирующую сладость 2a заносим в мультимножество. В противном случае удаляем из
мультимножества сладость а, сладость b оставляем.
if (2 * a
> b)
{
m.erase(m.begin());
m.insert(2*a);
}
}
Выводим ответ – максимально возможный уровень сладости.
printf("%lld\n",*m.begin());